Computers have historically been designed to execute instructions sequentially; that is, one after another. While sequential execution of computer instructions does provide a logical and orderly method of operation, the ever-present demand to increase processing speed has led to the development of computers that implement parallel execution of instructions. One category of such computers is referred to as a superscalar machine in which parallel instruction pipelines provide the ability to execute a plurality of instructions simultaneously, one in each pipeline.
There are numerous problems which must be overcome if one is to successfully design a computer or microprocessor which is capable of executing multiple instructions in parallel. For example, most microprocessors have an instruction set architecture which includes hundreds of individual instructions. Counting all of the different kinds of addressing modes for a given architecture, the total number of possible opcodes is likely to number somewhere in the thousands. Pairing all of the thousands of possible first instructions with all the possible second instructions for a given instruction set could easily result in millions of different combinations. Designing a machine which is capable of executing all of these various combinations is a formidable task. Fortunately, in most computer programs, a relatively small subset of the entire instruction set is used to generate a very high percentage of executable code. For the sake of simplicity, therefore, it is desirable to define a manageable set of instruction pairs that may be executed in parallel and to design the instruction pipelines accordingly. Pairs of instructions that are not members of the defined set must be executed sequentially.
Another problem confronting the designer of a superscalar machine is guaranteeing that the effect of parallel execution of instructions on the machine state visible to the programmer is the same as for sequential execution of the same set of instructions in a single pipeline. Unless this transparency can be guaranteed, code written for a conventional single pipeline microprocessor may not execute as desired in the superscalar machine.
One approach to this problem is to require that only independent instructions be permitted to enter the parallel pipelines simultaneously. A pair of instructions are "independent" if the execution of the second instruction in the pair does not utilize any machine resources that might be modified by execution of the first instruction in the pair. Potential dependencies between successive instructions include those involving general purpose registers, stack pointers, memory locations and flags. If successive instructions are not independent, they must be executed sequentially. This forgoes some of the performance increase theoretically possible with a superscalar design, but insures that code will execute reliably.
As will be seen, the present invention provides a method and apparatus for insuring that there are no dependencies between a pair of instructions that are presented for parallel execution in a superscalar machine.